package com.shm.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * 212. 单词搜索II
 * 给定一个 m x n 二维字符网格 board 和一个单词（字符串）列表 words，找出所有同时在二维网格和字典中出现的单词。
 *
 * 单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
 * 输出：["eat","oath"]
 * 示例 2：
 *
 *
 * 输入：board = [["a","b"],["c","d"]], words = ["abcb"]
 * 输出：[]
 *
 *
 * 提示：
 *
 * m == board.length
 * n == board[i].length
 * 1 <= m, n <= 12
 * board[i][j] 是一个小写英文字母
 * 1 <= words.length <= 3 * 104
 * 1 <= words[i].length <= 10
 * words[i] 由小写英文字母组成
 * words 中的所有字符串互不相同
 * @author SHM
 */
public class FindWords {
    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
    List<String> ans = new ArrayList<>();
    public List<String> findWords(char[][] board, String[] words) {
        Trie trie = new Trie();
        for (String word : words) {
            trie.insert(word);
        }
        int n = board.length;
        int m = board[0].length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                //如果当前字母不为前缀树开头，就没有必要进行dfs了
                if (trie.next[board[i][j]-'a']!=null){
                    boolean[][] visited = new boolean[n][m];
                    visited[i][j] = true;
                    dfs(i,j,n,m,visited,trie.next[board[i][j]-'a'],board);
                }
                //如果结果数组大小已等于单词词组大小，就可以提前结束
                if (ans.size()==words.length){
                    return ans;
                }
            }
        }
        return ans;
    }

    void dfs(int i,int j,int n,int m,boolean[][] visited,Trie trie,char[][] board){
        //当前节点的单词不为空，因此可以在结果中加入
        //在加入后将当前节点的单词置空是防止多次加入
        if (trie.sentence!=null&&!ans.contains(trie.sentence)){
            ans.add(trie.sentence);
            trie.sentence=null;
        }
        for (int k = 0; k < 4; k++) {
            int newI = i + dirs[k][0];
            int newY = j + dirs[k][1];
            //只有在对应前缀树的后续节点也不为空的前提下，才会继续进行dfs
            if (newI>=0&&newI<n&&newY>=0&&newY<m&&!visited[newI][newY]&&trie.next[board[newI][newY]-'a']!=null){
                visited[newI][newY]=true;
                dfs(newI,newY,n,m,visited,trie.next[board[newI][newY]-'a'],board);
                visited[newI][newY]=false;
            }
        }
    }

    class Trie{
        Trie[] next = new Trie[26];
        String sentence;

        Trie(){};

        void insert(String word){
            Trie node = this;
            char[] chars = word.toCharArray();
            for (char aChar : chars) {
                if (node.next[aChar-'a']==null){
                    node.next[aChar-'a']=new Trie();
                }
                node = node.next[aChar-'a'];
            }
            node.sentence=word;
        }

    }
}
